/* 2044. 统计按位或能得到最大值的子集数目 */
/**
 * @param {number[]} nums
 * @return {number}
 */
/* 
    位运算:
    记n是数组nums的长度,数组中的每个元素都可以选取或者不选择
    因此数组的非空子集数目一共有(2²[2 = n] - 1)个

    在整数的二进制表示中，n个比特的值代表了对数组不同元素的取舍 第i位值为
    1 表示该子集选取对应元素 第 i 位为0 则表示该子集不选取对应的元素，求出
    每个子集的按位或的值，并计算取到最大时的子集数
*/

var countMaxOrSubsets = function (nums) {
    let maxOr = 0, cnt = 0
    /* 
        i << j == 
        i * (2 ^ j)
    */
    for (let i = 0; i < 1 << nums.length; i++) {
        let orVal = 0
        for (let j = 0; j < nums.length; j++) {
            /* 
                (i >> j) & 1:
                等价于 i / ( 2 ^ j ) 然后与 1 做位运算
                如果最后一位为 1 就输出1 ，最后一位为 0 就输出0 
            */
            if (((i >> j) & 1)) {
                orVal |= nums[j]
            }
        }
        if (orVal > maxOr) {
            maxOr = orVal
            cnt = 1
        } else if (orVal === maxOr) {
            cnt++
        }
    }

    return cnt
};


/* dfs */
/**
 * @param {number[]} nums
 * @return {number}
 */
var countMaxOrSubsets = function (nums) {
    const len = nums.length;
    // 组合
    let res = 0, count = 0;
    function dfs (s, sum) {
        if (sum > res) {
            res = sum;
            count = 1;
        } else if (sum === res) count++;
        if (s === len) return;
        for (let i = s; i < len; ++i) {
            dfs(i + 1, sum | nums[i]);
        }
    }
    dfs(0, 0);
    return count;
};
